/*********************************************************************************
    This software is created under the term GNU General Public License.
    You should have received a copy of the GNU General Public License.
    If not, write to the Free Software Foundation, 59 Temple Place - Suite 330,
    Boston, MA 02111-1307, USA.

list_cir:
    a implement of list, using data structure double linked list. it is not a
    part of interface, but a part of implement of interface list. you
    can use it through interface list.

author: xiangyun.kong(lo-sor@hotmail.com)
create: 2-26-2011

changes:

**********************************************************************************/
#include "list_link.h"
#include <mem.h>
#include <assert.h>

ltl_iterator _ltl_new_node( ltl_iterator _pre, ltl_iterator _next, void *_val );
ltl_iterator _ltl_pos( list_link *_lt, int _pos );

list_link* ltl_create()
{
    list_link *_lt;
    _lt = (list_link *)palloc( sizeof(list_link) );
    assert( _lt != NULL );

    _lt->head = NULL;
    _lt->tail = NULL;
    _lt->size = 0;

    return _lt;
}

void ltl_destroy( list_link* _lt )
{
    list_link_node *_ltn, *t;
    _ltn = _lt->head;
    while( _ltn )
    {
        t = _ltn->next;
        pfree( _ltn );
        _ltn = t;
    }
    pfree( _lt );
}

int32 ltl_size( list_link* _lt )
{
    return _lt->size;
}

void ltl_pushb( list_link* _lt, void* _val )
{
    _lt->tail = _ltl_new_node( _lt->tail, NULL, _val );
}

void ltl_pushf( list_link *_lt, void *_val )
{
    _lt->head = _ltl_new_node( NULL, _lt->head, _val );
}

ltl_iterator ltl_insert( list_link *_lt, ltl_iterator _it, void *_val )
{
    ltl_iterator it;
    it = _ltl_new_node( _it, _it->next, _val );
    if( _it == _lt->tail )
        _lt->tail = it;
    return it;
}

ltl_iterator ltl_insertp( list_link *_lt, int32 _pos, void *_val )
{
    if( _pos <= 0 )
    {
        ltl_pushf( _lt, _val );
        return _lt->head;
    }
    else if( _pos >= ltl_size( _lt ) )
    {
        ltl_pushb( _lt, _val );
        return _lt->tail;
    }
    else
    {
        ltl_iterator _it = _ltl_pos( _lt, _pos );
        return ltl_insert( _lt, _it->pre, _val );
    }
}

void* ltl_val( ltl_iterator _it )
{
    return _it->val;
}

void* ltl_get( list_link *_lt, int32 _pos )
{
    if( _pos <= 0 )
        return ltl_front( _lt );
    else if( _pos >= ltl_size( _lt ) )
        return ltl_back( _lt );
    else
    {
        ltl_iterator _it = _ltl_pos( _lt, _pos );
        return ltl_val( _it );
    }
}

void* ltl_front( list_link *_lt )
{
    return ltl_val( _lt->head );
}

void* ltl_back( list_link *_lt )
{
    return ltl_val( _lt->tail );
}

ltl_iterator ltl_begin( list_link *_lt )
{
    return _lt->head;
}

ltl_iterator ltl_end( list_link *_lt )
{
    return NULL;
}

ltl_iterator ltl_next( ltl_iterator _it )
{
    return _it->next;
}

ltl_iterator ltl_pre( ltl_iterator _it )
{
    return _it->pre;
}

ltl_iterator ltl_find( list_link *_lt, void *_key, compare _fun )
{
    ltl_iterator _it;
    for( _it = ltl_begin(_lt); _it != ltl_end(_lt); _it = ltl_next(_it) )
    {
        if( 0 == _fun( _key, ltl_val( _it ) ) )
            return _it;
    }
    return NULL;

}

void* ltl_popf( list_link *_lt )
{
    ltl_iterator _it;
    void *_val = NULL;
    _it = ltl_begin( _lt );
    _lt->head = _it->next;
    _lt->head->pre = NULL;
    if( _it != NULL )
    {
        _val = ltl_val( _it );
        pfree( _it );
    }
    return _val;
}

void* ltl_popb( list_link *_lt )
{
    ltl_iterator _it;
    void *_val = NULL;
    _it = _lt->tail;
    _lt->tail = _it->pre;
    _lt->tail->next = NULL;
    if( _it != NULL )
    {
        _val = ltl_val( _it );
        pfree( _it );
    }
    return _val;
}

void* ltl_remove( list_link *_lt, ltl_iterator _it )
{
    if( _it == ltl_begin( _lt ) )
        return ltl_popf( _lt );
    else if( _it == _lt->tail )
        return ltl_popb( _lt );
    else
    {
        void *_val = ltl_val( _it );
        _it->pre->next = _it->next;
        _it->next->pre = _it->pre;
        pfree( _it );
        return _val;
    }
}

void* ltl_removep( list_link *_lt, int32 _pos )
{
    if( _pos <= 0 )
        return ltl_popf( _lt );
    else if( _pos >= ltl_size( _lt ) )
        return ltl_popb( _lt );
    else
    {
        ltl_iterator _it = _ltl_pos( _lt, _pos );
        return ltl_remove( _lt, _it );
    }
}

ltl_iterator _ltl_new_node( ltl_iterator _pre, ltl_iterator _next, void *_val )
{
    ltl_iterator _it;
    _it = (ltl_iterator) palloc( sizeof( list_link_node ) );
    assert( _it != NULL );

    _it->val = _val;
    _it->pre = _pre;
    _it->next = _next;
    if( _pre )
        _pre->next = _it;
    if( _next )
        _next->pre = _it;
    return _it;
}

ltl_iterator _ltl_pos( list_link *_lt, int _pos )
{
    ltl_iterator _it;
    _it = ltl_begin( _lt );
    while( _pos-- > 0 )
        _it = ltl_next( _it );
    return _it;
}

void ltl_sort( list_link *_lt, compare _fun )
{
    list_link_node *sorted, *unsorted;

    if( _lt->size < 2 )
        return;

    sorted = _lt->head;
    unsorted = _lt->head->next;
    while( sorted != _lt->tail )
    {
        unsorted = sorted;
        while( unsorted != _lt->tail )
        {
            if( _fun(sorted->val, unsorted->val) > 0 )
            {
                (long)sorted->val ^= (long)unsorted->val;
                (long)unsorted->val ^= (long)sorted->val;
                (long)sorted->val ^= (long)unsorted->val;
            }
            unsorted = unsorted->next;
        }
        sorted = sorted->next;
    }
}
